/*
 * @Author: wwssaabb
 * @Date: 2021-11-27 14:24:36
 * @LastEditTime: 2021-11-27 15:25:17
 * @FilePath: \handwritten-code\algorithm\两数之和.js
 */

/* 
给定一个整数数组 nums 和一个整数目标值 target， 请你在该数组中找出 和为目标值 target 的那 两个 整数， 并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。 但是， 数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1：

输入： nums = [2, 7, 11, 15], target = 9
输出：[0, 1]
解释： 因为 nums[0] + nums[1] == 9， 返回[0, 1]。
示例 2：

输入： nums = [3, 2, 4], target = 6
输出：[1, 2]
示例 3：

输入： nums = [3, 3], target = 6
输出：[0, 1]

来源： 力扣（ LeetCode）
链接： https: //leetcode-cn.com/problems/two-sum
*/
console.time(1)
//for遍历，map存储，空间复杂度O(n)、时间复杂度O(n)Map开支

var twoSum = function (nums, target) {
  let map = new Map([
    [target - nums[0], 0]
  ])
  for (let i = 1; i < nums.length; i++) {
    if (map.has(nums[i])) return [map.get(nums[i]), i]
    map.set(target - nums[i], i)
  }
}


//for遍历，map存储，空间复杂度O(n)、时间复杂度O(n)对象属性开支

var twoSum = function (nums, target) {
  let map = {
    [target - nums[0]]: 0
  }
  for (let i = 1; i < nums.length; i++) {
    if (map[nums[i]]) return [+map[nums[i]], +i]
    map[target - nums[i]] = i
  }
}



//for嵌套for 空间复杂度O(1)、时间复杂度O(n^2)
var twoSum = function (nums, target) {
  for (let i = 0; i < nums.length; i++) {
    for (let x = i + 1; x < nums.length; x++)
      if (target - nums[x] === nums[i]) return [i, x]
  }
}



console.timeEnd(1)

console.log(twoSum([2, 7, 11, 15], 9)) //[0,1]
console.log(twoSum([2, 8, 11, 15, 7], 9)) //[0,4]